/*
day279
2020.6.2
*/
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<deque>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        map<TreeNode*,TreeNode*> m;
        vector<int> res;
        deque<TreeNode *> que;
        set<TreeNode *> s;
        
        
        record(root,m);
        que.push_back(target);
        s.insert(target);
		
		for(int i=0;i<K;++i)
		{
			int size=que.size();
			for(int q=0;q<size;++q)
			{
				TreeNode *tem=que.front();
				que.pop_front();
				
				if(tem->left && s.find(tem->left)!=s.end())
				{
					s.insert(tem->left);
					que.push_back(tem->left);
				}
				
				if(tem->right && s.find(tem->right)!=s.end())
				{
					s.insert(tem->right);
					que.push_back(tem->right);
				}
				
				TreeNode *father=m[tem];
				if(father && s.find(father)!=s.end())
				{
					s.insert(father);
					que.push_back(father);
				}
			}
		 } 
		 
		 while(!que.empty())
		 {
		 	res.push_back(que.front()->val);
		 	que.pop_front();
		 }
        
        return res;
    }
    
    
    void record(TreeNode *root,map<TreeNode*,TreeNode*> &m)
    {
    	if(!root)
    	{
    		return ;
		}
		
		if(root->left)
		{
			m[root->left]=root;
		}
		
		if(root->right)
		{
			m[root->right]=root;
		}
		
		record(root->left,m);
		record(root->right,m);
	}
};

int main()
{
	return 0;
}
